1923D - Slimes - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 1;
int T, n, a[N], cnt[N];
ll s[N];

int read()
{
    int x = 0;
    char c = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        x = (x << 3) + (x << 1) + (c & 15), c = getchar();
    return x;
}
int main()
{
    T = read();
    while (T--)
    {
        n = read();
        for (int i = 1; i <= n; i++)
            a[i] = read(), s[i] = s[i - 1] + a[i];
        for (int i = 2; i <= n; i++)
            cnt[i] = cnt[i - 1] + (a[i] != a[i - 1]);
        for (int i = 1; i <= n; i++)
        {
            int l = 1, r = i - 1;
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                if (s[i - 1] - s[mid - 1] > a[i] && (a[i - 1] > a[i] || cnt[i - 1] - cnt[mid]))
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            int ans = r > 0 ? i - r : INT_MAX;
            l = i + 1, r = n;
            while (l <= r)
            {
                int mid = (l + r) >> 1;
                if (s[mid] - s[i] > a[i] && (a[i + 1] > a[i] || cnt[mid] - cnt[i + 1]))
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            ans = min(ans, l > n ? INT_MAX : l - i);
            printf("%d ", ans == INT_MAX ? -1 : ans);
        }
        putchar('\n');
    }
    return 0;
}